/*
    XTU OJ: 1108
    by: fifth_light
*/

#include <stdio.h>

int num_conv(char* num, int base) {
    char* pnt = num;
    int neg = 0;
    int result = 0;
    while (*pnt != '\0') {
        result *= base;
        if (*pnt == '-') {
            neg = !neg;
        } else if (*pnt >= '0' && *pnt <= '9') {
            result += *pnt - '0';
        } else if (*pnt >= 'A' && *pnt <= 'Z') {
            result += *pnt - 'A' + 10;
        } else if (*pnt >= 'a' && *pnt <= 'z') {
            result += *pnt - 'a' + 36;
        }
        pnt++;
    }
    return neg ? -result : result;
}

int main(void) {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        char a[64], b[64];
        int base_a, base_b;
        if (scanf(" %63[0-9a-zA-Z-] %d %63[0-9a-zA-Z-] %d",
            a, &base_a, b, &base_b) == EOF) {
            break;
        }
        int num_a = num_conv(a, base_a);
        int num_b = num_conv(b, base_b);
        printf("%d\n", num_a + num_b);
    }
    return 0;
}
